package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/rotate-list">旋转链表(Rotate List)</a>
 * <p>给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4,5], k = 2
 *                      1   ->  2   ->  3   ->  4   ->  5
 *          rotate1     5   ->  1   ->  2   ->  3   ->  4
 *          rotate      4   ->  5   ->  1   ->  2   ->  3
 *      输出：[4,5,1,2,3]
 *
 * 示例 2：
 *      输入：head = [0,1,2], k = 4
 *                      0   ->  1   ->  2
 *          rotate1     2   ->  0   ->  1
 *          rotate2     1   ->  2   ->  0
 *          rotate3     0   ->  1   ->  2
 *          rotate4     2   ->  0   ->  1
 *      输出：[2,0,1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *      <li>链表中节点的数目在范围 [0, 500] 内</li>
 *      <li>-100 <= Node.val <= 100</li>
 *      <li>0 <= k <= 2 * 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/4/27 10:30
 */
public class LC0061RotateList_M {
    static class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            // 空链表 或 只有一个节点 或向右移动0个位置，直接返回
            if (head == null || head.next == null || k == 0) {
                return head;
            }
            // 统计链表中节点的个数。如果是k的倍数，向右移动nk次相当于没移动，直接返回
            int size = 0;
            ListNode currNode = head;
            while (currNode != null) {
                ++size;
                currNode = currNode.next;
            }
            if ((k %= size) == 0) {
                return head;
            }
            // 通过快慢指针查找倒数第k-1个节点
            // 快慢指针，让快指针先走k步，然后快慢指针同时走，快指针走到链表尾部，此时慢指针的下一个节点就是新的链表头节点。
            ListNode fast = head;
            ListNode slow = head;
            for (int i = 0; i < k; i++) {
                fast = fast.next;
            }
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            // 此时slow位于k-1的位置，fast位于原链表的尾节点
            // slow的下一个节点为移动后的新节点
            ListNode newHead = slow.next;
            slow.next = null;
            fast.next = head;
            return newHead;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.rotateRight(Generator.create(1, 2, 3, 4, 5), 2));
        Printer.printListNode(solution.rotateRight(Generator.create(0, 1, 2), 4));
    }
}